SEYMOUR, Circuit Judge.

Ahmed Khalfan Ghailani is a prisoner at the United States Penitentiary, Administrative Maximum Facility in Florence, Colorado ("ADX Florence"). He was subjected to Special Administrative Measures ("SAMs") that limited his contact with the outside world due to his past terrorist activities and his connections with terrorist groups. One of the restrictions included a prohibition against participating in group prayer. Mr. Ghailani, as a pro se plaintiff, challenged the legality of his numerous restrictions. He requested a declaratory judgment proclaiming that the government's imposition and enforcement of the restrictions violated numerous constitutional provisions as well as the Religious Freedom and Restoration Act ("RFRA"), 42 U.S.C. § 2000bb. He also sought an injunction ordering the government to permit his participation in group prayer. The district court dismissed his suit for failure to state a claim. While his case was on appeal, the government allowed Mr. Ghailani's SAMs to expire. But he is still prohibited from participating in group prayer due to the housing restrictions at ADX Florence, a high security prison.

We reverse for the reasons set out below.

I.

This case has its origin in the 1998 United States embassy bombings in Kenya and Tanzania, in which 224 people were killed and thousands were injured. United States v. Ghailani, 733 F.3d 29, 39 (2d Cir. 2013). Mr. Ghailani was an Al-Queda operative and part of the terror cell that perpetrated those bombings but, unlike several of his co-conspirators, he eluded authorities for six years before he was finally captured in 2004. Id. In 2006, he was transferred to Guantanamo Bay Detention Center and remained there until 2009, when he was transferred to New York, arraigned, and held in the Metropolitan Correctional Center while he awaited trial. Id. at 40.

Mr. Ghailani was first subjected to SAMs upon his arrival in New York. SAMs are tools used to limit privileges for certain federal inmates. 28 C.F.R. § 501.3(a). They may be imposed if there is a finding "of a substantial risk that a prisoner's ... contacts with persons could result in death or serious bodily injury to persons, or substantial damage to property that would entail the risk of death or serious bodily injury to persons." Id. The SAMs must be "reasonably necessary to protect persons against the risk of acts of violence or terrorism." Id. Moreover, they must be based on findings specific to the inmate which demonstrate the risk posed by the inmate's contacts and communications. The Attorney General must first instruct the Director of the Bureau of Prisons to issue the SAMs, and then the Director authorizes the prison warden to enforce them. Id. SAMs have a one-year limit and the only way they may be extended is upon written notification from the Attorney General stating that "there continues to be a substantial risk that the inmate's communications or contacts with other persons could result in death or serious bodily injury to persons, or substantial damage to property that would entail the risk of death or serious bodily injury to persons." § 501.3(c). The inmate must be provided written notification of the basis for the SAMs, § 501.3(b), and an inmate subject to SAMs may seek administrative review of his restrictions, § 501.3(e).

After his conviction, Mr. Ghailani was transferred to ADX Florence, where he remains today. His 2009 SAMs were extended every year through June 10, 2015. Imposition of each of the SAMs was justified by the Attorney General on the basis of Mr. Ghailani's "central role" in the embassy bombing, his "connections to and proclivity for terrorism," and his "notoriety and ability to inspire and influence others to engage in acts of violence and terrorism." 2014 SAM, ROA, vol. I at 276-77.1 In light of those concerns, the SAMs imposed limitations on Mr. Ghailani's contacts and communications that "could reasonably foreseeably result in [his] communicating information (sending or receiving) that could circumvent the SAM's intent of significantly limiting [his] ability to communicate (send or receive) terrorism-related information." Id. at 278. In addition to numerous specified limitations on his contacts with others both inside and outside the prison, the SAMs also specifically incorporated by reference all restrictive policies of the prison. Id. at 277. Most significantly for our present purposes, Mr. Ghailani was prohibited from engaging in group prayer with other inmates in accordance with his religion.

In January 2014, Mr. Ghailani filed a six-count complaint in the district court. He challenged the SAMs on various grounds. He also challenged the prison's "policy created specifically to target plaintiff's ability to freely exercise his religion." Id. at 186. His religious exercise challenge was brought under both the First Amendment and RFRA and was based on the prohibition on his "participat[ing] in group prayer." Id. at 183. Mr. Ghailani sought to "pray Jumu'ah prayer" — which is a Muslim group prayer that occurs once a week and involves "five daily prayers in group," id. at 186 — but he was forbidden to do so. The remaining claims were all based solely on the SAMs and they included (1) a First Amendment claim challenging the deprivation of his right to use the mail to contact his friends, family, and sometimes his attorney; (2) a First Amendment claim challenging a SAM provision that prohibited him from talking to the news media; (3) a Fifth Amendment Due Process claim arguing that the SAMs constituted an atypical and significant hardship and deprived him of a significant liberty interest without due process; (4) an Eighth Amendment claim contending the SAMs provision that required his solitary confinement was cruel and unusual punishment; and (5) a Fifth Amendment claim arguing that the imposition and re-imposition of the SAMs violated the Fifth Amendment's prohibition of Double Jeopardy.

The government filed a motion to dismiss. On November 3, 2014, the magistrate judge recommended dismissal of all of Mr. Ghailani's First Amendment claims and his RFRA claim because he failed to allege "sufficient facts to indicate the plausibility that the actions of which he complains were not reasonably related to legitimate penological interests." ROA, vol. I at 425 (quoting Gee v. Pacheco, 627 F.3d 1178, 1188 (10th Cir. 2010) (emphasis in original)). The judge recommended dismissal of Mr. Ghailani's Fifth Amendment claim because he "failed to allege facts demonstrating that the SAMs implicate a liberty interest," id. at 427, and dismissal of Mr. Ghailani's Eighth Amendment claim because his complaint "failed to allege an `unquestioned and serious deprivation of basic human needs' or `intolerable or shocking conditions,'" id. at 429 (quoting Hill v. Pugh, 75 Fed.Appx. 715, 721 (10th Cir. 2003) (unpublished)). Finally, the magistrate judge recommended dismissal of Mr. Ghailani's Double Jeopardy claim because the SAMs did not arise out of criminal proceedings and the "risk to which the [Double Jeopardy] Clause refers is not present in proceedings that are not `essentially criminal.'" Id. at 430 (alteration in original) (quoting Breed v. Jones, 421 U.S. 519, 528, 95 S.Ct. 1779, 44 L.Ed.2d 346 (1975)).

On January 30, 2015, the district court determined that "Magistrate Judge Boland's Report and Recommendation is correct and is not called into question by Plaintiff's objection," id. at 533, and granted the government's motion to dismiss with prejudice. Mr. Ghailani appeals.2

II.

A. Mootness

A majority of Mr. Ghailani's request for relief focused on the SAMs. On June 10, 2015, however, Mr. Ghailani's 2014 SAMs expired and they were not renewed. The government therefore contends Mr. Ghailani's claims are moot.

"We review mootness de novo as a legal question." United States v. Fisher, 805 F.3d 982, 989 (10th Cir. 2015). In cases involving mootness, "[t]he starting point for [our] analysis is the familiar proposition that `federal courts are without power to decide questions that cannot affect the rights of litigants in the case before them.'" DeFunis v. Odegaard, 416 U.S. 312, 316, 94 S.Ct. 1704, 40 L.Ed.2d 164 (1974) (quoting North Carolina v. Rice, 404 U.S. 244, 246, 92 S.Ct. 402, 30 L.Ed.2d 413, (1971)). The mootness doctrine "derives from the requirement of Art. III of the Constitution under which the exercise of judicial power depends upon the existence of a case or controversy." Id. The Supreme Court has described it as "the doctrine of standing set in a time frame: The requisite personal interest that must exist at the commencement of the litigation (standing) must continue throughout its existence (mootness)." U.S. Parole Comm'n v. Geraghty, 445 U.S. 388, 397, 100 S.Ct. 1202, 63 L.Ed.2d 479 (1980) (quoting Henry P. Monaghan, Constitutional Adjudication: The Who and When, 82 Yale L.J. 1363, 1384 (1973)). "The crucial question is whether granting a present determination of the issues offered will have some effect in the real world." Wyoming v. U.S. Dep't of Agric., 414 F.3d 1207, 1212 (10th Cir. 2005) (quoting Citizens for Responsible Gov't State Political Action Comm. v. Davidson, 236 F.3d 1114, 1223 (10th Cir. 2001)). "Put another way, a case becomes moot `when a plaintiff no longer suffers "actual injury that can be redressed by a favorable judicial decision."'" Ind v. Colo. Dep't of Corr., 801 F.3d 1209, 1213 (10th Cir. 2015) (quoting Rhodes v. Judiscak, 676 F.3d 931, 933(10th Cir. 2012)).

But there are certain exceptions to mootness where "a case remains subject to federal court jurisdiction notwithstanding the seeming extinguishment of any live case or controversy." Brown v. Buhman, 822 F.3d 1151, 1166 (10th Cir. 2016). Mr. Ghailani argues that two of those exceptions are applicable in this case. We will address each in turn.

1. Capable of Repetition Yet Evading Review

Courts will not find a case moot if the issue is deemed a wrong capable of repetition yet evading review. This exception applies where "(1) the challenged action is in its duration too short to be fully litigated prior to cessation or expiration; and (2) there is a reasonable expectation that the same complaining party will be subject to the same action again." FEC v. Wis. Right to Life, Inc., 551 U.S. 449, 462, 127 S.Ct. 2652, 168 L.Ed.2d 329 (2007) (quoting Spencer v. Kemna, 523 U.S. 1, 17, 118 S.Ct. 978, 140 L.Ed.2d 43 (1998)).

Mr. Ghailani contends this exception applies here, relying on our decision in Al-Owhali v. Holder, 687 F.3d 1236 (10th Cir. 2012). In Al-Owhali, an inmate challenged the constitutionality of a SAM that prevented him from subscribing to two Arabic-language newspapers. Id. at 1239. By the time his case was on appeal, his SAMs had been amended and no longer included the newspaper restriction. Id. at 1241-42. We nevertheless held the issue was not moot because it was capable of repetition yet evading review. Id. at 1242. We reasoned that "[i]f we prohibited any challenge to a lapsed SAM, inmates would only have one year to litigate and appeal a case. This feat will often be impossible, as this case illustrates: Years have elapsed since Al-Owhali first brought his claim." Id. As to whether there was a reasonable expectation that Mr. Al-Owhali would be subjected to the same action again, we concluded that "there is nothing preventing the government from introducing more restrictive SAMs in any given year" and a "prisoner can reasonably expect SAMs to change from year to year and fluctuate in severity." Id.

Al-Owhali makes clear that SAMs are generally too short in duration to be fully litigated before expiration. But there is a significant distinction between Mr. Al-Owhali's situation and the one here. Mr. Al-Owhali's SAMs never completely expired. Instead, they just changed somewhat from year to year. Id. at 1242. Accordingly, the factual justification supporting imposition of the SAMs remained current. In the present case, however, the Attorney General has allowed Mr. Ghailani's SAMs to completely expire. As the government explained at oral argument, the reason why Mr. Ghailani's SAMs were eliminated was because the majority of his co-conspirators involved in the embassy bombings "have been either captured or killed," Mr. Ghailani has exhibited "good conduct" while in prison, "his notoriety and his ability to inspire others" has waned with the passage of time, and he was the only conspirator who expressed remorse for his actions. Oral Argument at 16:32-17:10. Accordingly, the Attorney General no longer believes "that there continues to be a substantial risk that [his] communications or contacts with other persons could result in death or serious bodily injury to persons." 28 C.F.R. § 501.3(c).

To hold that there is a reasonable expectation the government will re-impose SAMs on Mr. Ghailani would require us to find that it has withdrawn them for almost two years while still believing that all the risks justifying the SAMs still exist, just to win a case on mootness that it already won below on the merits. We decline to do so. In the circumstances here, we are persuaded there is no reasonable expectation that Mr. Ghailani will be subjected to SAMs again.

2. Voluntary Cessation

As we recognized in Ind, 801 F.3d at 1214:

"[A] defendant claiming that its voluntary compliance moots a case bears the formidable burden of showing that it is absolutely clear the allegedly wrongful behavior could not reasonably be expected to recur." Friends of the Earth, Inc. v. Laidlaw Envtl. Servs., Inc., 528 U.S. 167, 190, 120 S.Ct. 693, 145 L.Ed.2d 610 (2000) (quoting United States v. Concentrated Phosphate Export Ass'n., 393 U.S. 199, 203, 89 S.Ct. 361, 21 L.Ed.2d 344 (1968)).

A defendant's voluntary actions may nevertheless moot litigation if two conditions are met: "(1) it can be said with assurance that there is no reasonable expectation that the alleged violation will recur, and (2) interim relief or events have completely and irrevocably eradicated the effects of the alleged violation." County of Los Angeles v. Davis, 440 U.S. 625, 631, 99 S.Ct. 1379, 59 L.Ed.2d 642 (1979) (internal quotation marks, ellipsis, and citations omitted). Significantly for our purposes, "[c]ourts are more apt to trust public officials than private defendants to desist from future violations." 13C CHARLES ALAN WRIGHT, ARTHUR R. MILLER & EDWARD H. COOPER, FEDERAL PRACTICE AND PROCEDURE, § 3533.7 at 333(3d ed. 2008) (citing cases). Accordingly, we "have indicated that government `self-correction provides a secure foundation for mootness so long as it seems genuine.'" Buhman, 822 F.3d at 1167-68 (quoting Rio Grande Silvery Minnow v. Bureau of Reclamation, 601 F.3d 1096, 1118 (10th Cir. 2010)).

We conclude here that the government's voluntary cessation has met the conditions listed in Davis. First, as we explained above, it is unlikely the government suspended SAMs on a prisoner whom it thought posed a threat of serious bodily injury to American citizens just to moot a case it won below on the merits. We have been given no reason to question the good faith of the government in the explanation it gave us.

As to the second Davis condition, there is no evidence that any of the former SAM restrictions are currently affecting Mr. Ghailani. While he is still being denied the ability to pray Jumu'ah, that prohibition "is consistent with ... the housing conditions at the ADX," Defendants' Motion to Dismiss, ROA vol. I at 256, and it continues despite the expiration of the SAMs.

We conclude that all of the claims Mr. Ghailani has raised relating to his SAM restrictions are moot.3

B. Mr. Ghailani's Claim That He is Not Allowed to Pray Jumu'ah

Even without the SAMs in place, Mr. Ghailani is still prohibited from praying Jumu'ah in prison due to the ADX Florence housing conditions. "Jumu'ah is commanded by the Koran and must be held every Friday after the sun reaches its zenith and before the Asr, or afternoon prayer." O'Lone v. Estate of Shabazz, 482 U.S. 342, 345, 107 S.Ct. 2400, 96 L.Ed.2d 282 (1987). The government asserts that we should dismiss this issue as insufficiently raised and require that Mr. Ghailani bring a new action if he wants to challenge the prison policies. Mr. Ghailani counters by arguing that his pro se complaint challenged not only the SAMs but also "the policy created specifically to target [his] ability to freely exercise his religion." ROA, vol. I at 186. We agree.

First, while Mr. Ghailani asked the court to grant four different requests for relief, only three mentioned the SAMs. One asked the court to review the constitutionality of 28 C.F.R. § 501.3; another one asked the court to issue multiple declaratory judgments stating that the SAMs violated numerous constitutional provisions; and the third asked the court to issue a preliminary injunction ordering the government to refrain from reimposing the SAMs until resolution of the case. In the last request, however, Mr. Ghailani specifically asked the court to "issue an injunction ordering defendants to ... [a]llow Plaintiff to participate in group prayer" and to "[a]ccommodate plaintiff with a place to exercise his religion." Id. at 199. Second, "[a] pro se litigant's pleadings are to be construed liberally and held to a less stringent standard than formal pleadings drafted by lawyers." Hall v. Bellmon, 935 F.2d 1106, 1110 (10th Cir. 1991). As Mr. Ghailani points out on appeal, the government admitted in its brief to the district court that "the group prayer ban is consistent with the other provisions in Ghailani's SAMs and the housing conditions at ADX. ..." ROA, vol. I at 256. (emphasis added). We will therefore review Mr. Ghailani's claim that he is being denied his rights under the First Amendment and RFRA by the prison's group prayer ban.

We review a district court's dismissal of a claim under the Federal Rules of Civil Procedure, 12(b)(6) de novo. Khalik v. United Air Lines, 671 F.3d 1188, 1190 (10th Cir. 2012). A pleading that states a claim for relief must contain "a short and plain statement of the claim showing that the pleader is entitled to relief." FED. R. CIV. P. 8(a)(2). In a pair of Supreme Court cases discussing the requirements of Rule 8, Bell Atlantic Corp. v. Twombly, 550 U.S. 544, 545-46, 127 S.Ct. 1955, 167 L.Ed.2d 929 (2007), and Ashcroft v. Iqbal, 556 U.S. 662, 129 S.Ct. 1937, 173 L.Ed.2d 868 (2009), the Court established a heightened pleading requirement for federal civil cases. The Court stated that "[t]hreadbare recitals of the elements of a cause of action, supported by mere conclusory statements," would no longer suffice to "unlock the doors of discovery," and "only a complaint that states a plausible claim for relief [will] survive a motion to dismiss." Iqbal, 556 U.S. at 678-79, 129 S.Ct. 1937 (citing Twombly, 550 U.S. at 555-57, 127 S.Ct. 1955).

Interpreting the standard set forth in Twombly and Iqbal, we held in Gee, 627 F.3d at 1188, that a prisoner alleging a violation of his First Amendment rights "must include sufficient facts to indicate the plausibility that the actions of which he complains were not reasonably related to legitimate penological interests." The "legitimate penological interests" language comes from Turner v. Safley, 482 U.S. 78, 89, 107 S.Ct. 2254, 96 L.Ed.2d 64 (1987), where the Supreme Court departed from its traditional First Amendment framework set forth in Sherbert v. Verner, 374 U.S. 398, 403, 83 S.Ct. 1790, 10 L.Ed.2d 965 (1963) (holding any incidental burden on somebody's free exercise of religion must be justified by a "compelling state interest"), and held instead that "when a prison regulation impinges on inmates' constitutional rights, the regulation is valid if it is reasonably related to legitimate penological interests."

The district court dismissed Mr. Ghailani's religious freedom claim with prejudice on the basis that he failed to meet the requirements of Gee in his complaint, i.e., that he did not include facts showing the regulations restricting his ability to pray Jumu'ah were not related to a legitimate penological interest. We agree with this analysis as applied to Mr. Ghailani's First Amendment claim. However, Mr. Ghailani also pled that the restriction on his ability to pray was a violation of RFRA. The district court erred in applying the same pleading requirement to the RFRA claim as it did to the constitutional religious freedom claim.4

Some background on RFRA and the cases interpreting it is helpful to illustrate why this is so. RFRA's enactment was the direct result of the Supreme Court's decision in Employment Division Department of Human Resources of Oregon v. Smith, 494 U.S. 872, 110 S.Ct. 1595, 108 L.Ed.2d 876 (1990), where the Court introduced a new test for evaluating claims brought under the Free Exercise Clause of the First Amendment. Instead of applying the strict scrutiny standard that was introduced in Verner, the Court held in Smith that the First Amendment does not "relieve an individual of the obligation to comply with a `valid and neutral law of general applicability.'" Id. at 879, 110 S.Ct. 1595 (quoting United States v. Lee, 455 U.S. 252, 263 n.3, 102 S.Ct. 1051, 71 L.Ed.2d 127 (1982)).

Congress enacted RFRA to overturn Smith. Finding that "laws `neutral' toward religion may burden religious exercise as surely as laws intended to interfere with religious exercise," 42 U.S.C. § 2000bb(a)(2), Congress "restore[d] the compelling interest test as set forth in Sherbert v. Verner, 374 U.S. 398, 83 S.Ct. 1790, 10 L.Ed.2d 965 (1963) and Wisconsin v. Yoder, 406 U.S. 205, 92 S.Ct. 1526, 32 L.Ed.2d 15 (1972) and ... guarantee[d] its application in all cases where free exercise of religion is substantially burdened," id. § 2000bb(b)(1). See also Gonzales v. O Centro Espirita Beneficente Uniao do Vegetal, 546 U.S. 418, 424, 126 S.Ct. 1211, 163 L.Ed.2d 1017 (2006). Accordingly, RFRA's main provision reads as follows:

Id. § 2000bb-1(a)-(b) (emphasis added).5

The text of RFRA left open the question whether the government's compelling interest burden would apply in the prisoner context, as opposed to the relaxed standard introduced in Turner. We resolved that issue in Kikumura v. Hurley, 242 F.3d 950, 962 (10th Cir. 2001), where we held that "neither the text, nor the legislative history of RFRA suggest that [the] relaxed standard [from Turner] applies to the government's burden when a prisoner makes a RFRA claim." We explained the difference between a prisoner's religious freedom claim brought under the First Amendment versus one brought under RFRA as follows:

Id. Because the Turner standard does not apply to a RFRA claim, a prisoner-plaintiff clearly need not plead facts showing "that the actions of which he complains were not reasonably related to legitimate penological interests," as Gee required for First Amendment claims. Accordingly, while the district court properly dismissed Mr. Ghailani's First Amendment claim alleging that the prison violated his free exercise rights by not allowing him to pray Jumu'ah, it erred in dismissing his RFRA claim.

Moreover, just as Mr. Ghailani did not need to plead facts showing the government lacked a legitimate penological interest, he also did not need to plead facts showing that the restrictions were not in "furtherance of a compelling governmental interest" and were not "the least restrictive means of furthering that compelling governmental interest." 42 U.S.C. § 2000bb-1(b)(1)-(2). Subsection (b) of RFRA is an "affirmative defense," and "the burden is placed squarely on the Government by RFRA." Gonzales, 546 U.S. at 429, 126 S.Ct. 1211; see also Gomez v. Toledo, 446 U.S. 635, 640, 100 S.Ct. 1920, 64 L.Ed.2d 572 (1980) ("the burden of pleading [affirmative defenses] rests with the defendant." (citing FED. R. CIV. P. 8(c))); Levin v. Miller, 763 F.3d 667, 671 (7th Cir. 2014) ("The Court held in Gomez... that complaints need not anticipate affirmative defenses; neither Iqbal nor Twombly suggests otherwise").

Finally, the government argues that by attaching the SAMs to his complaint, Mr. Ghailani provided the court with proof that the government had a compelling interest in the free exercise limitation that it applied in the least restrictive way, thus setting out the government's affirmative defense which Mr. Ghailani should have then negated. We are skeptical of the merits of this argument because the compelling interest test cannot "be satisfied by the government's bare say-so." Yellowbear v. Lampert, 741 F.3d 48, 59 (10th Cir. 2014). Regardless, the government has admitted that the factual basis for the SAMs, the risk that Mr. Ghailani imposed because of his terrorist activities in 1998, has expired. The government's argument thus expired with the SAMs and the burden remains on it to affirmatively demonstrate that denying Mr. Ghailani the right to freely exercise his religion by praying Jumu'ah once a week is in furtherance of a compelling governmental interest in the least restrictive manner.

Accordingly, we REVERSE the decision of the district court granting the government's motion to dismiss Mr. Ghailani's SAMs claims and REMAND with instructions to dismiss those claims as moot. We also REVERSE the district court's dismissal of Mr. Ghailani's RFRA claim and REMAND for further proceedings in accordance with this opinion.